package com.qch.edu.lagou.sort;

/**
 * @Author qch
 * @Date 2021/7/21
 * 5.计数排序
 */
public class CountSort {
    public static int[] countSort(int[] array, int offset) {
        int[] nums = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            int n = (array[i] - offset);
            //数字自增
            //90(1),91(2),92(1),93(1),94(1),95(1),96(0),97(0),98(1),99(2)
            //nums:1,2,1,1,1,1,0,0,1,2
            nums[n]++;
        }
        int[] nums2 = new int[array.length];
        // i是计数数组下标，k是新数组下标
        //将统计的个数，按照位置+偏移量恢复原数据，并按照统计的个数set进新数组
        for (int i = 0, k = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i]; j++) {
                nums2[k++] = i + offset;
            }
        }
        return nums2;
    }

    public static void main(String[] args) {
        int[] scores = {95, 94, 91, 98, 99, 90, 99, 93, 91, 92};
        for (int n : countSort(scores, 90)) {
            System.out.println(n);
        }
    }
}
